457. Circular Array Loop

Similar Question

leading to the advanced question

Solution Tips

方案一: 判圈思路

var circularArrayLoop = function (nums) {
    for (let i = 0; i < nums.length; i++) {
        // fast 走两步, slow 走一步, 迟早会相遇
        // 相遇之后再计算循环步数, 也就是环的长度, 只要长度大于 1 就可以返回 true
        let slow = i;
        let fast = i;

        do {
            // 走两步
            fast = nextStep(fast);
            fast = nextStep(fast);

            slow = nextStep(slow);
        } while (slow !== fast);

        // slow 走一圈, 计算步数
        let count = 0;
        // 保证同号
        let prev = slow;
        do {
            prev = slow;
            slow = nextStep(slow);
            if (nums[slow] * nums[prev] < 0) break;
            count++;
        } while (slow !== fast);

        if (nums[slow] * nums[prev] > 0 && count > 1) return true;

        function nextStep(index) {
            index = (index + nums[index]) % nums.length;

            return index >= 0 ? index : nums.length + index;
        }
    }

    return false;
};

console.log(circularArrayLoop([1, -1, 5, 1, 4]))
console.log(circularArrayLoop([2,-1,1,2,2]))
console.log(circularArrayLoop([-1,2]))
console.log(circularArrayLoop([-2,1,-1,-2,-2]))

方案二: by case 优化

按照题意, 数组里是一定有环的, 每个元素开启遍历都一定有环.

遍历的过程必须是单向的, 所以快慢指针第一次走的时候就可以判断方向了